#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <cassert>
#include <utility>

using namespace std;


const unsigned int ASCII_A = 97;
const unsigned int ASCII_Z = ASCII_A + 26;
const bool         _DEBUG = false;

typedef size_t                            etat_t;
typedef unsigned char                     symb_t;
typedef set< etat_t >                     etatset_t;
typedef vector< vector< etatset_t > >     trans_t;
typedef vector< etatset_t >               epsilon_t;
typedef map< etatset_t, etat_t >          map_t;


////////////////////////////////////////////////////////////////////////////////

struct sAutoNDE{
  // caractéristiques
  size_t nb_etats;
  size_t nb_symbs;
  size_t nb_finaux;
  
  etat_t initial;
  // état initial
  
  etatset_t finaux;
  // états finaux : finaux_t peut être un int*, un tableau dynamique comme vector<int>
  // ou une autre structure de donnée de votre choix.
  
  trans_t trans;
  // matrice de transition : trans_t peut être un int***, une structure dynamique 3D comme vector< vector< set<int> > >
  // ou une autre structure de donnée de votre choix.
  
  epsilon_t epsilon;
  // transitions spontanées : epsilon_t peut être un int**, une structure dynamique 2D comme vector< set<int> >
  // ou une autre structure de donnée de votre choix.
};

////////////////////////////////////////////////////////////////////////////////

bool FromFile(sAutoNDE& at, string path){
  ifstream myfile(path.c_str(), ios::in);
  //un flux d'entree obtenu à partir du nom du fichier
  string line;
  // un ligne lue dans le fichier avec getline(myfile,line);
  istringstream iss;
  // flux associé à la chaine, pour lire morceau par morceau avec >> (comme cin)
  etat_t s(0), t(0);
  // deux états temporaires
  symb_t a(0);
  // un symbole temporaire
  
  if (myfile.is_open()){
    // la première ligne donne 'nb_etats nb_symbs nb_finaux'
    do{
      getline(myfile,line);
    } while (line.empty() || line[0]=='#');
    // on autorise les lignes de commentaires : celles qui commencent par '#'
    iss.str(line);
    if((iss >> at.nb_etats).fail() || (iss >> at.nb_symbs).fail() || (iss >> at.nb_finaux).fail())
      return false;
    // la deuxième ligne donne l'état initial
    do{
      getline (myfile,line);
    } while (line.empty() || line[0]=='#');
    iss.clear();
    iss.str(line);
    if((iss >> at.initial).fail())
      return -1;
    
    // les autres lignes donnent les états finaux
    for(size_t i = 0; i < at.nb_finaux; i++){
      do{
        getline (myfile,line);
      } while (line.empty() || line[0]=='#');
      iss.clear();
      iss.str(line);
      if((iss >> s).fail())
        continue;
      cerr << "s= " << s << endl;
      at.finaux.insert(s);
    }
    
    // on alloue les vectors à la taille connue à l'avance pour éviter les resize dynamiques
    at.trans.resize(at.nb_etats);
    for(size_t i=0;i<at.nb_etats;++i)
      at.trans[i].resize(at.nb_symbs);
    
    // lecture de la relation de transition
    while(myfile.good()){
      line.clear();
      getline (myfile,line);
      if (line.empty() && line[0]=='#')
        continue;
      iss.clear();
      iss.str(line);
      
      // si une des trois lectures echoue, on passe à la suite
      if((iss >> s).fail() || (iss >> a).fail() || (iss >> t).fail() || (a< ASCII_A ) || (a> ASCII_Z ))
        continue;
      
      //test espilon ou non
      if ((a-ASCII_A) >= at.nb_symbs){
        cerr << "s=" << s<< ", (e), t=" << t << endl;
        //TODO remplir epsilon
      }
      else{
        cerr << "s=" << s<< ", a=" << a-ASCII_A << ", t=" << t << endl;
        //TODO remplir trans
      }
    }
    myfile.close();
    return true;
  }
  return false;
  // on ne peut pas ouvrir le fichier
}


// -----------------------------------------------------------------------------
// Fonctions complétées pour le TP2
// -----------------------------------------------------------------------------


////////////////////////////////////////////////////////////////////////////////

bool ContientFinal(const sAutoNDE& at,const etatset_t& e){
  for(etatset_t::const_iterator it=e.cbegin(); it != e.cend(); ++it)
  {
  //parcours des deux ensembles
  	for(etatset_t::const_iterator it1=at.finaux.cbegin(); it1 != at.finaux.cend(); ++it1)
		{
  		if(*it==*it1)
  		{
  		//si on trouve deux états égaux, on retourne vrai
  			return true;
			}	
		}
	}
  return false;
}

////////////////////////////////////////////////////////////////////////////////

bool EstDeterministe(const sAutoNDE& at){
	for(size_t i=0;i<at.nb_etats;++i)
	{
		if(at.epsilon[i].size()>1)
			return false;
		// si pour un état donné, on peut accéder a plusieurs états avec epsilon on retourne faux
		for(size_t j=0;j<at.nb_symbs;++j)
		{
		// on parcours la table de transition 
      if(at.trans[i][j].size()>1) 
      	return false;
      	// si pour un état donné et un caractère donné, l'ensemble d'états auquels on peut accéder est supérieur a 1
  			// on retourne faux
    }
	}
  return true;
}



////////////////////////////////////////////////////////////////////////////////

void Fermeture(const sAutoNDE& at, etatset_t& e){
  // Cette fonction clot l'ensemble d'états E={e_0, e_1, ... ,e_n} passé en 
  // paramètre avec les epsilon transitions
  for(etatset_t::const_iterator it=e.cbegin(); it != e.cend(); ++it)
  {
  		for(etatset_t::const_iterator it1=at.epsilon[*it].cbegin(); it1 != at.epsilon[*it].cend(); ++it1)
  		{
  			// on parcours epsilon avec les états de l'ensembles e, on ajoute dans e 
  			//les états auquels on peut avoir acces a partir de ces états
  			e.insert(*it1);
  		}
	}
}


////////////////////////////////////////////////////////////////////////////////

etatset_t Delta(const sAutoNDE& at, const etatset_t& e, symb_t c){
  //TODO sur la base de celle pour le cas sans transitions spontanées, 
  // définir cette fonction en utilisant Fermeture
  etatset_t p,q;
  p=e;
  //on effectue la fermeture de l'ensemble e, et on l'enregistre dans l'ensemble d'états p
  Fermeture(at,p);
  for(etatset_t::const_iterator it=p.cbegin(); it != p.cend(); ++it)
  {
  	// on parcours l'ensemble des états de p apres fermeture
  	if(!(at.trans[*it][c-ASCII_A].empty()))
  		q.insert(at.trans[*it][c-ASCII_A].begin(),at.trans[*it][c-ASCII_A].end());
  		// on insère dans l'ensemble d'états q, les états auquels on peut avoir acces a partir d'un des états de p
  		// avec le caractère c
  }
  Fermeture(at,q);
  // on effectue la fermeture de l'ensemble d'états obtenus
  return q;
}

////////////////////////////////////////////////////////////////////////////////

bool Accept(const sAutoNDE& at, string str){
  etatset_t p;
  p.insert(at.initial);  
  // on prend l'état initial dans l'ensemble
  for (size_t i=0;i<str.size();i++)
  {
  // on parcourt la chaine de caractères
        p=Delta(at,p,str[i]);
        // on retient l'ensemble d'états auquels on peut accéder
  }
  return (ContientFinal(at, p));
  // si apres le parcours de la chaine l'ensemble d'états p contient un des états finaux, on retourne vrai
}

////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// Fonctions à compléter pour le TP3
// -----------------------------------------------------------------------------


ostream& operator<<(ostream& out, const sAutoNDE& at){
  //TODO définir cette fonction
  
  return out;
}

////////////////////////////////////////////////////////////////////////////////

bool ToGraph(sAutoNDE& at, string path){
  //TODO définir cette fonction
  
  return false;
}

////////////////////////////////////////////////////////////////////////////////

pair<sAutoNDE,map_t> Determinize(const sAutoNDE& at){
  sAutoNDE r;
  map_t m;
  
  //TODO définir cette fonction
  
  return (pair<sAutoNDE,map_t>(r,m));
}

////////////////////////////////////////////////////////////////////////////////

// fonction outil : on garde x, et on "ajoute" trans et epsilon de y
// en renommant ses états, id est en décalant les indices des états de y
// de x.nb_etats
sAutoNDE Append(const sAutoNDE& x, const sAutoNDE& y){
  assert(x.nb_symbs == y.nb_symbs);
  sAutoNDE r;
  
  //TODO définir cette fonction
  
  return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Union(const sAutoNDE& x, const sAutoNDE& y){
  assert(x.nb_symbs == y.nb_symbs);
  sAutoNDE r = Append(x, y);
  
  //TODO définir cette fonction
  
  return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Concat(const sAutoNDE& x, const sAutoNDE& y){
  assert(x.nb_symbs == y.nb_symbs);
  sAutoNDE r = Append(x, y);
  
  //TODO définir cette fonction
  
  return r;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Complement(const sAutoNDE& x){
  //TODO définir cette fonction
  
  return x;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Kleene(const sAutoNDE& x){
  //TODO définir cette fonction
  
  return x;
}

////////////////////////////////////////////////////////////////////////////////

sAutoNDE Intersection(const sAutoNDE& x, const sAutoNDE& y){
  //TODO définir cette fonction
  
  return x;
}

////////////////////////////////////////////////////////////////////////////////

void Help(ostream& out, char *s){
  out << "Utilisation du programme " << s << " :" << endl ;
  out << "-det ou -determinize Input :\n\t déterminise Input" << endl;
  out << "-cup ou -union Input1 Input2 :\n\t calcule l'union" << endl;
  out << "-cat ou -concat Input1 Input2 :\n\t calcul la concaténation" << endl;
  out << "-star ou -kleene Input :\n\t calcul de A*" << endl;
  out << "-bar ou -complement Input :\n\t calcul du complément" << endl;
  out << "-cap ou -intersection Input1 Input2 :\n\t calcul de l'intersection" << endl;
  out << "-acc ou -accept Input Word:\n\t détermine si le mot Word est accepté" << endl;
  out << "-nop ou -no_operation Input :\n\t ne rien faire de partiulier" << endl;
  
  out << "-o ou -output Output :\n\t écrire le résultat dans le fichier Output, afficher sur STDOUT si non spécifié" << endl;
  out << "-g ou -graphe :\n\t l'output est au format dot/graphiz" << endl  << endl;
  
  out << "Exemple '" << s << " -determinize auto.txt -output determin.txt'" << endl;
}

////////////////////////////////////////////////////////////////////////////////

int main(int argc, char* argv[] ){
  if(argc < 3){
    Help(cout, argv[0]);
    return EXIT_FAILURE;
  }
  
  long pos;
  long act=-1;                 // pos et act pour savoir quelle action effectuer
  bool files = false;         // option à un seul ou deux fichiers ?
  string str, in1, in2, out, acc;
  // chaines pour (resp.) tampon; fichier d'entrée Input1; fichier d'entrée Input2;
  // fichier de sortie et chaine dont l'acceptation est à tester
  bool toFile, graphMode;     // sortie STDOUT ou fichier ? Si fichier, format graphviz ?
  
  // options acceptées
  const size_t NBOPT = 10;
  string aLN[] = {"determinize", "union", "concat", "kleene", "complement", "intersection", "accept", "no_operation", "output", "graph"};
  string aSN[] = {"det", "cup", "cat", "star", "bar", "cap", "acc", "nop", "o", "g"};
  
  // on essaie de "parser" chaque option de la ligne de commande
  for(int i=1; i<argc; ++i){
    if (_DEBUG) cerr << "argv[" << i << "] = '" << argv[i] << "'" << endl;
    str = argv[i];
    pos = -1;
    string* pL = find(aLN, aLN+NBOPT, str.substr(1));
    string* pS = find(aSN, aSN+NBOPT, str.substr(1));
    
    if(pL!=aLN+NBOPT)
      pos = pL - aLN;
    if(pS!=aSN+NBOPT)
      pos = pS - aSN;
    
    if(pos != -1){
      // (pos != -1) <=> on a trouvé une option longue ou courte
      if (_DEBUG) cerr << "Key found (" << pos << ") : " << str << endl;
      switch (pos) {
        case 0: //det
          in1 = argv[++i];
          break;
        case 1: //cup
          in1 = argv[++i];
          in2 = argv[++i];
          files = true;
          break;
        case 2: //cat
          in1 = argv[++i];
          in2 = argv[++i];
          files = true;
          break;
        case 3: //star
          in1 = argv[++i];
          break;
        case 4: //bar
          in1 = argv[++i];
          break;
        case 5: //cap
          in1 = argv[++i];
          in2 = argv[++i];
          files = true;
          break;
        case 6: //acc
          in1 = argv[++i];
          acc = argv[++i];
          break;
        case 7: //nop
          in1 = argv[++i];
          break;
        case 8: //o
          toFile = true;
          out = argv[++i];
          break;
        case 9: //g
          graphMode = true;
          break;
        default:
          return EXIT_FAILURE;
      }
    }
    else{
      cerr << "Option inconnue "<< str << endl;
      return EXIT_FAILURE;
    }
    
    if(pos<8){
      if(act > -1){
        cerr << "Plusieurs actions spécififées"<< endl;
        return EXIT_FAILURE;
      }
      else
        act = pos;
    }
  }
  
  if (act == -1){
    cerr << "Pas d'action spécififée"<< endl;
    return EXIT_FAILURE;
  }
  
  // Les options sont OK, on va essayer de lire le(s) automate(s) at1 (et at2)
  //   et effectuer l'action spécifiée. Atr stockera le résultat
  
  sAutoNDE at1, at2, atr;
  pair<sAutoNDE,map_t> d;
  
  if (!FromFile(at1, in1)){
    cerr << "Erreur de lecture " << in1 << endl;
    return EXIT_FAILURE;
  }
  if (files and !FromFile(at2, in2)){
    cerr << "Erreur de lecture " << in2 << endl;
    return EXIT_FAILURE;
  }
  
  switch(act) {
    case 0: //det
      d = Determinize(at1);
      atr = d.first;
      break;
    case 1: //cup
      atr =  Union(at1, at2);
      break;
    case 2: //cat
      atr =  Concat(at1, at2);
      break;
    case 3: //star
      atr =  Kleene(at1);
      break;
    case 4: //bar
      atr =  Complement(at1);
      break;
    case 5: //cap
      atr =  Intersection(at1, at2);
      break;
    case 6: //acc
      cout << "'" << acc << "' est accepté: " << Accept(at1, acc) << endl;
      atr = at1;
      break;
    case 7: //nop
      atr = at1;
      break;
    default:
      return EXIT_FAILURE;
  }
  
  // on affiche le résultat ou on l'écrit dans un fichier
  if(!toFile)
    // affichage
    cout << atr;
  else{
    if(graphMode){
      // génération du graphe
      ToGraph(atr, out + ".gv");
      system(("dot -Tpng " + out + ".gv -o " + out + ".png").c_str());
    }
    else{
      // génération du fichier
      ofstream f(out.c_str(), ios::trunc);
      if(f.fail())
        return EXIT_FAILURE;
      f << atr;
    }
  }
  
  return EXIT_SUCCESS;
}



